home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / route.arc / SOLVE.C < prev    next >
C/C++ Source or Header  |  1989-11-24  |  14KB  |  426 lines
  1. #include <stdio.h>
  2.  
  3. #ifndef M_XENIX
  4. #include <stdlib.h>
  5. #include <io.h>
  6. #endif 
  7.  
  8. #include <fcntl.h>
  9. #include "cell.h"
  10.  
  11. /*
  12. ** visit neighboring cells like this (where [9] is on the other side):
  13. **
  14. **    +---+---+---+
  15. **    | 1 | 2 | 3 |
  16. **    +---+---+---+
  17. **    | 4 |[9]| 5 |
  18. **    +---+---+---+
  19. **    | 6 | 7 | 8 |
  20. **    +---+---+---+
  21. */
  22.  
  23. static int delta[8][2] = { /* for visiting neighbors on the same side */
  24.      {  1, -1 }, /* northwest    */
  25.      {  1,  0 }, /* north        */
  26.      {  1,  1 }, /* northeast    */
  27.      {  0, -1 }, /* west        */
  28.      {  0,  1 }, /* east        */
  29.      { -1, -1 }, /* southwest    */
  30.      { -1,  0 }, /* south        */
  31.      { -1,  1 }  /* southeast    */
  32.     };
  33.  
  34. static int ndir[8] = { /* for building paths back to source */
  35.      FROM_SOUTHEAST, FROM_SOUTH, FROM_SOUTHWEST,
  36.      FROM_EAST,                  FROM_WEST,
  37.      FROM_NORTHEAST, FROM_NORTH, FROM_NORTHWEST
  38.     };
  39.  
  40. /* blocking masks for neighboring cells */
  41. #define BLOCK_NORTHEAST        ( DIAG_NEtoSW | BENT_StoNE | BENT_WtoNE \
  42.                 | ANGLE_NEtoSE | ANGLE_NWtoNE \
  43.                 | SHARP_NtoNE | SHARP_EtoNE )
  44. #define BLOCK_SOUTHEAST        ( DIAG_SEtoNW | BENT_NtoSE | BENT_WtoSE \
  45.                 | ANGLE_NEtoSE | ANGLE_SEtoSW \
  46.                 | SHARP_EtoSE | SHARP_StoSE )
  47. #define BLOCK_SOUTHWEST        ( DIAG_NEtoSW | BENT_NtoSW | BENT_EtoSW \
  48.                 | ANGLE_SEtoSW | ANGLE_SWtoNW \
  49.                 | SHARP_StoSW | SHARP_WtoSW )
  50. #define BLOCK_NORTHWEST        ( DIAG_SEtoNW | BENT_EtoNW | BENT_StoNW \
  51.                 | ANGLE_SWtoNW | ANGLE_NWtoNE \
  52.                 | SHARP_WtoNW | SHARP_NtoNW )
  53.  
  54. struct block {
  55.     int r1, c1;
  56.     long b1, h1;
  57.     int r2, c2;
  58.     long b2, h2;
  59.     };
  60.  
  61. static struct block blocking[8] = { /* blocking masks */
  62.      {  0, -1, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  63.         1,  0, BLOCK_SOUTHWEST, HOLE_SOUTHWEST },
  64.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  65.      {  1,  0, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  66.         0,  1, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  67.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  68.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  69.      {  0, -1, BLOCK_SOUTHEAST, HOLE_SOUTHEAST,
  70.        -1,  0, BLOCK_NORTHWEST, HOLE_NORTHWEST },
  71.      {  0,  0, 0, 0, 0, 0, 0, 0 },
  72.      { -1,  0, BLOCK_NORTHEAST, HOLE_NORTHEAST,
  73.         0,  1, BLOCK_SOUTHWEST, HOLE_SOUTHWEST }
  74.     };
  75.  
  76. static int selfok[5][8] = { /* mask for self-blocking corner effects */
  77.      { 1, 1, 1, 1, 1, 1, 1, 1 },
  78.      { 0, 0, 0, 0, 1, 0, 1, 0 },
  79.      { 0, 0, 0, 1, 0, 0, 1, 0 },
  80.      { 0, 1, 0, 0, 1, 0, 0, 0 },
  81.      { 0, 1, 0, 1, 0, 0, 0, 0 }
  82.     };
  83.  
  84. static long newmask[5][8] = { /* patterns to mask out in neighbor cells */
  85.      { 0, 0, 0, 0, 0, 0, 0, 0 },
  86.      { 0, 0, 0, 0, CORNER_NORTHEAST | CORNER_SOUTHEAST, 0,
  87.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  88.      { 0, 0, 0, CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0,
  89.         CORNER_SOUTHEAST | CORNER_SOUTHWEST, 0 },
  90.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0, 0,
  91.         CORNER_NORTHEAST | CORNER_SOUTHEAST, 0, 0, 0 },
  92.      { 0, CORNER_NORTHEAST | CORNER_NORTHWEST, 0,
  93.         CORNER_SOUTHWEST | CORNER_NORTHWEST, 0, 0, 0, 0 }
  94.     };
  95.  
  96. static char fmt[] =
  97.   "  open=%ld, closed=%ld, moved=%ld, max=%ld, %ld%% of board";
  98.  
  99. /* board dimensions */
  100. extern int Nrows;
  101. extern int Ncols;
  102.  
  103. /* measures of progress */
  104. int Ntotal = 0;
  105. int Ncurrent = 0;
  106.  
  107. /* search statistics */
  108. extern long OpenNodes; /* total number of nodes opened */
  109. extern long ClosNodes; /* total number of nodes closed */
  110. extern long MoveNodes; /* total number of nodes moved */
  111. extern long MaxNodes; /* maximum number of nodes opened at one time */
  112.  
  113. extern void GetWork( int *, int *, char far * far *, int *, int *,
  114.     char far * far * );
  115.  
  116. extern void InitQueue( void );
  117. extern void GetQueue( int *, int *, int *, int *, int * );
  118. extern void SetQueue( int, int, int, int, int, int, int );
  119. extern void ReSetQueue( int, int, int, int, int, int, int );
  120. extern long GetCell( int, int, int );
  121. extern void SetCell( int, int, int, long );
  122. extern void OrCell( int, int, int, long );
  123. extern int GetDir( int, int, int );
  124. extern void SetDir( int, int, int, int );
  125. extern int GetDist( int, int, int );
  126. extern void SetDist( int, int, int, int );
  127. extern int GetApxDist( int, int, int, int );
  128. extern int CalcDist( int, int, int );
  129.  
  130. void Solve( void );
  131. void Retrace( int, int, int, int, int );
  132.  
  133. void Solve () { /* route all traces */
  134.     int r1, c1, r2, c2, r, c, s, d, a, nr, nc, skip;
  135.     int i;
  136.     char far *n1;
  137.     char far *n2;
  138.     long curcell, newcell, buddy, lastopen, lastclos, lastmove;
  139.     int newdist, olddir, success, self, echo;
  140.  
  141.     printf( "enter Solve()\n" );
  142.     echo = isatty( fileno(stdout) ) ? 1 : 0;
  143.     /* go until no more work to do */
  144.     for (GetWork( &r1, &c1, &n1, &r2, &c2, &n2 ); r1 != ILLEGAL;
  145.             GetWork( &r1, &c1, &n1, &r2, &c2, &n2 )) {
  146.         Ncurrent++;
  147.         printf( "routing %Fs=%Fs, %d of %d\n", n1, n2, Ncurrent,
  148.             Ntotal );
  149.         if (r1 == r2 && c1 == c2) /* trivial case; already routed */
  150.             continue;
  151.         success = 0;
  152.         lastopen = lastclos = lastmove = 0;
  153.         InitQueue(); /* initialize the search queue */
  154.         a = GetApxDist( r1, c1, r2, c2 ); /* rough estimate */
  155.         SetQueue( r1, c1, TOP, 0, a, r2, c2 );
  156.         SetQueue( r1, c1, BOTTOM, 0, a, r2, c2 );
  157.         /* search until success or we exhaust all possibilities */
  158.         for (GetQueue( &r, &c, &s, &d, &a ); r != ILLEGAL;
  159.             GetQueue( &r, &c, &s, &d, &a )) {
  160.             if (r == r2 && c == c2) { /* success! */
  161.                 Retrace( r1, c1, r2, c2, s ); /* lay traces */
  162.                 success++;
  163.                 break;
  164.                 }
  165.             /* report every 100 new nodes or so */
  166.             if (echo && (OpenNodes - lastopen > 100
  167.                 || ClosNodes - lastclos > 100
  168.                 || MoveNodes - lastmove > 100)) {
  169.                 lastopen = (OpenNodes/100)*100;
  170.                 lastclos = (ClosNodes/100)*100;
  171.                 lastmove = (MoveNodes/100)*100;
  172.                 printf( fmt, OpenNodes, ClosNodes,
  173.                     MoveNodes, MaxNodes,
  174.                     (ClosNodes*50)/(Nrows*Ncols) );
  175.                 putchar( '\r' );
  176.                 }
  177.             curcell = GetCell( r, c, s );
  178.             if (curcell & CORNER_NORTHWEST)
  179.                 self = 1;
  180.             else if (curcell & CORNER_NORTHEAST)
  181.                 self = 2;
  182.             else if (curcell & CORNER_SOUTHWEST)
  183.                 self = 3;
  184.             else if (curcell & CORNER_SOUTHEAST)
  185.                 self = 4;
  186.             else
  187.                 self = 0;
  188.             for (i = 0; i < 8; i++) { /* consider neighbors */
  189.                 if (!selfok[self][i]) /* check self-block */
  190.                     continue;
  191.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  192.                     || (nc = c+delta[i][1]) < 0
  193.                     || nc >= Ncols) /* off the edge? */
  194.                     continue;
  195.                 newcell = GetCell( nr, nc, s );
  196.                 /* check for non-target hole */
  197.                 if (newcell & HOLE) {
  198.                     if (nr != r2 || nc != c2)
  199.                         continue;
  200.                     }
  201.                 else {
  202.                     newcell &= ~(newmask[self][i]);
  203.                     if (newcell) /* check for traces */
  204.                         continue;
  205.                     }
  206.                 /* check blocking on corner neighbors */
  207.                 if (delta[i][0] && delta[i][1]) {
  208.                     /* check first buddy */
  209.                     buddy = GetCell( r+blocking[i].r1,
  210.                         c+blocking[i].c1, s );
  211.                     if (buddy & HOLE) {
  212.                         if (buddy & (blocking[i].h1))
  213.                             continue;
  214.                         }
  215.                     else if (buddy & (blocking[i].b1))
  216.                         continue;
  217.                     /* check second buddy */
  218.                     buddy = GetCell( r+blocking[i].r2,
  219.                         c+blocking[i].c2, s );
  220.                     if (buddy & HOLE) {
  221.                         if (buddy & (blocking[i].h2))
  222.                             continue;
  223.                         }
  224.                     else if (buddy & (blocking[i].b2))
  225.                         continue;
  226.                     }
  227.                 olddir = GetDir( r, c, s );
  228.                 newdist = d+CalcDist( ndir[i], olddir,
  229.                     (olddir == FROM_OTHERSIDE)
  230.                     ? GetDir( r, c, 1-s ) : 0 );
  231.                 /* if not visited yet, add it to queue */
  232.                 if (!GetDir( nr, nc, s )) {
  233.                     SetDir( nr, nc, s, ndir[i] );
  234.                     SetDist( nr, nc, s, newdist );
  235.                     SetQueue( nr, nc, s, newdist,
  236.                         GetApxDist( nr, nc, r2, c2 ),
  237.                         r2, c2 );
  238.                     }
  239.                 /* we might have found a better path */
  240.                 else if (newdist < GetDist( nr, nc, s )) {
  241.                     SetDir( nr, nc, s, ndir[i] );
  242.                     SetDist( nr, nc, s, newdist );
  243.                     ReSetQueue( nr, nc, s, newdist,
  244.                         GetApxDist( nr, nc, r2, c2 ),
  245.                         r2, c2 );
  246.                     }
  247.                 }
  248.             /* consider other side of board */
  249.             /* check for holes or traces on other side */
  250.             if (newcell = GetCell( r, c, 1-s ))
  251.                 continue;
  252.             skip = 0;
  253.             /* check for nearby holes */
  254.             for (i = 0; i < 8; i++) {
  255.                 if ((nr = r+delta[i][0]) < 0 || nr >= Nrows
  256.                     || (nc = c+delta[i][1]) < 0
  257.                     || nc >= Ncols) /* off the edge? */
  258.                     continue;
  259.                 if (GetCell( nr, nc, s ) & HOLE) {
  260.                     skip = 1; /* neighboring hole */
  261.                     break;
  262.                     }
  263.                 }
  264.             if (skip) /* neighboring hole? */
  265.                 continue; /* yes, can't drill one here */
  266.             olddir = GetDir( r, c, s );
  267.             newdist = d+CalcDist( FROM_OTHERSIDE, olddir,
  268.                 (olddir == FROM_OTHERSIDE)
  269.                 ? GetDir( r, c, 1-s ) : 0 );
  270.             /* if not visited yet, add it to queue */
  271.             if (!GetDir( r, c, 1-s )) {
  272.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  273.                 SetDist( r, c, 1-s, newdist );
  274.                 SetQueue( r, c, 1-s, newdist, a, r2, c2 );
  275.                 }
  276.             /* we might have found a better path */
  277.             else if (newdist < GetDist( r, c, 1-s )) {
  278.                 SetDir( r, c, 1-s, FROM_OTHERSIDE );
  279.                 SetDist( r, c, 1-s, newdist );
  280.                 ReSetQueue( r, c, 1-s, newdist, a, r2, c2 );
  281.                 }
  282.             }
  283.         printf( fmt, OpenNodes, ClosNodes, MoveNodes, MaxNodes,
  284.             (ClosNodes*50)/(Nrows*Ncols) );
  285.         putchar( '\n' );
  286.         if (!success)
  287.             printf( "\t*!* UNSUCCESSFUL *!*\n" );
  288.         /* clear direction flags */
  289.         for (r = 0; r < Nrows; r++) {
  290.             for (c = 0; c < Ncols; c++) {
  291.                 SetDir( r, c, TOP, EMPTY );
  292.                 SetDir( r, c, BOTTOM, EMPTY );
  293.                 }
  294.             }
  295.         }
  296.     printf( "leave Solve()\n" );
  297.     }
  298.  
  299. static long bit[8][9] = { /* OT=Otherside */
  300.      /* N, NE, E, SE, S, SW, W, NW, OT */
  301. /* N */  { LINE_VERTICAL, BENT_StoNE, CORNER_SOUTHEAST, SHARP_StoSE, 0,
  302.        SHARP_StoSW, CORNER_SOUTHWEST, BENT_StoNW, (HOLE | HOLE_SOUTH) },
  303. /* NE */ { BENT_NtoSW, DIAG_NEtoSW, BENT_EtoSW, ANGLE_SEtoSW, SHARP_StoSW,
  304.        0, SHARP_WtoSW, ANGLE_SWtoNW, (HOLE | HOLE_SOUTHWEST) },
  305. /* E */  { CORNER_NORTHWEST, BENT_WtoNE, LINE_HORIZONTAL, BENT_WtoSE,
  306.        CORNER_SOUTHWEST, SHARP_WtoSW, 0, SHARP_WtoNW, (HOLE | HOLE_WEST) },
  307. /* SE */ { SHARP_NtoNW, ANGLE_NWtoNE, BENT_EtoNW, DIAG_SEtoNW, BENT_StoNW,
  308.        ANGLE_SWtoNW, SHARP_WtoNW, 0, (HOLE | HOLE_NORTHWEST) },
  309. /* S */  { 0, SHARP_NtoNE, CORNER_NORTHEAST, BENT_NtoSE, LINE_VERTICAL,
  310.        BENT_NtoSW, CORNER_NORTHWEST, SHARP_NtoNW, (HOLE | HOLE_NORTH) },
  311. /* SW */ { SHARP_NtoNE, 0, SHARP_EtoNE, ANGLE_NEtoSE, BENT_StoNE, DIAG_NEtoSW,
  312.        BENT_WtoNE, ANGLE_NWtoNE, (HOLE | HOLE_NORTHEAST) },
  313. /* W */  { CORNER_NORTHEAST, SHARP_EtoNE, 0, SHARP_EtoSE, CORNER_SOUTHEAST,
  314.        BENT_EtoSW, LINE_HORIZONTAL, BENT_EtoNW, (HOLE | HOLE_EAST) },
  315. /* NW */ { BENT_NtoSE, ANGLE_NEtoSE, SHARP_EtoSE, 0, SHARP_StoSE,
  316.            ANGLE_SEtoSW, BENT_WtoSE, DIAG_SEtoNW, (HOLE | HOLE_SOUTHEAST) }
  317.     };
  318.  
  319. void Retrace ( rr1, cc1, rr2, cc2, s )
  320.     /* work from target back to source, actually laying the traces */
  321.     int rr1, cc1, rr2, cc2, s; /* start on side s */
  322.     {
  323.     int r0, c0, s0, r1, c1, s1, r2, c2, s2;
  324.     register int x, y;
  325.     long b;
  326.  
  327.     r1 = rr2;
  328.     c1 = cc2;
  329.     s1 = s;
  330.     r0 = c0 = s0 = ILLEGAL;
  331.     do {
  332.         /* find where we came from to get here */
  333.         switch (x = GetDir( r2 = r1, c2 = c1, s2 = s1 )) {
  334.         case FROM_NORTH:    r2++;        break;
  335.         case FROM_EAST:            c2++;    break;
  336.         case FROM_SOUTH:    r2--;        break;
  337.         case FROM_WEST:            c2--;    break;
  338.         case FROM_NORTHEAST:    r2++;    c2++;    break;
  339.         case FROM_SOUTHEAST:    r2--;    c2++;    break;
  340.         case FROM_SOUTHWEST:    r2--;    c2--;    break;
  341.         case FROM_NORTHWEST:    r2++;    c2--;    break;
  342.         case FROM_OTHERSIDE:    s2 = 1-s2;    break;
  343.         default:
  344.             printf( "internal error: no way back\n" );
  345.             exit( -1 );
  346.             break;
  347.             }
  348.         if (r0 != ILLEGAL)
  349.             y = GetDir( r0, c0, s0 );
  350.         /* see if target or hole */
  351.         if ((r1 == rr2 && c1 == cc2) || (s1 != s0)) {
  352.             switch (x) {
  353.             case FROM_NORTH:
  354.                 OrCell( r1, c1, s1, HOLE_NORTH );    break;
  355.             case FROM_EAST:
  356.                 OrCell( r1, c1, s1, HOLE_EAST );    break;
  357.             case FROM_SOUTH:
  358.                 OrCell( r1, c1, s1, HOLE_SOUTH );    break;
  359.             case FROM_WEST:
  360.                 OrCell( r1, c1, s1, HOLE_WEST );    break;
  361.             case FROM_NORTHEAST:
  362.                 OrCell( r1, c1, s1, HOLE_NORTHEAST );    break;
  363.             case FROM_SOUTHEAST:
  364.                 OrCell( r1, c1, s1, HOLE_SOUTHEAST );    break;
  365.             case FROM_SOUTHWEST:
  366.                 OrCell( r1, c1, s1, HOLE_SOUTHWEST );    break;
  367.             case FROM_NORTHWEST:
  368.                 OrCell( r1, c1, s1, HOLE_NORTHWEST );    break;
  369.             case FROM_OTHERSIDE:
  370.             default:
  371.                 printf( "internal error\n" );
  372.                 exit( -1 );
  373.                 break;
  374.                 }
  375.             }
  376.         else {
  377.             if ((y == FROM_NORTH || y == FROM_NORTHEAST
  378.                 || y == FROM_EAST || y == FROM_SOUTHEAST
  379.                 || y == FROM_SOUTH || y == FROM_SOUTHWEST
  380.                 || y == FROM_WEST || y == FROM_NORTHWEST)
  381.                 && (x == FROM_NORTH || x == FROM_NORTHEAST
  382.                 || x == FROM_EAST || x == FROM_SOUTHEAST
  383.                 || x == FROM_SOUTH || x == FROM_SOUTHWEST
  384.                 || x == FROM_WEST || x == FROM_NORTHWEST
  385.                 || x == FROM_OTHERSIDE)
  386.                 && (b = bit[y-1][x-1])) {
  387.                 OrCell( r1, c1, s1, b );
  388.                 if (b & HOLE)
  389.                     OrCell( r2, c2, s2, HOLE );
  390.                 }
  391.             else {
  392.                 printf( "internal error\n" );
  393.                 exit( -1 );
  394.                 }
  395.             }
  396.         if (r2 == rr1 && c2 == cc1) { /* see if source */
  397.             switch (x) {
  398.             case FROM_NORTH:
  399.                 OrCell( r2, c2, s2, HOLE_SOUTH );    break;
  400.             case FROM_EAST:
  401.                 OrCell( r2, c2, s2, HOLE_WEST );    break;
  402.             case FROM_SOUTH:
  403.                 OrCell( r2, c2, s2, HOLE_NORTH );    break;
  404.             case FROM_WEST:
  405.                 OrCell( r2, c2, s2, HOLE_EAST );    break;
  406.             case FROM_NORTHEAST:
  407.                 OrCell( r2, c2, s2, HOLE_SOUTHWEST );    break;
  408.             case FROM_SOUTHEAST:
  409.                 OrCell( r2, c2, s2, HOLE_NORTHWEST );    break;
  410.             case FROM_SOUTHWEST:
  411.                 OrCell( r2, c2, s2, HOLE_NORTHEAST );    break;
  412.             case FROM_NORTHWEST:
  413.                 OrCell( r2, c2, s2, HOLE_SOUTHEAST );    break;
  414.             case FROM_OTHERSIDE:
  415.             default:
  416.                 printf( "internal error\n" );
  417.                 exit( -1 );
  418.                 break;
  419.                 }
  420.             }
  421.         /* move to next cell */
  422.         r0 = r1; c0 = c1; s0 = s1;
  423.         r1 = r2; c1 = c2; s1 = s2;
  424.         } while (!(r2 == rr1 && c2 == cc1));
  425.     }
  426.